package 动态规划_斐波那列;

public class 解码方法_91 {
/**
 * 一条包含字母 A-Z 的消息通过以下方式进行了编码：
		
		'A' -> 1
		'B' -> 2
		...
		'Z' -> 26
		给定一个只包含数字的非空字符串，请计算解码方法的总数。
		
		示例 1:
		
		输入: "12"
		输出: 2
		解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。
		示例 2:
		
		输入: "226"
		输出: 3
		解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
 * 
 */
	
	/*
	 * 
	 * 
	 * 如果string中没有‘0’的存在，这道题就是简单的爬楼梯问题LeetCode70——Climbing Stairs， 
		并且其动归方程可以简单的记为：dp(i+1)=dp(i)+dp(i-1)
		
		其中dp(i)表示s[0]到s[i-1]这一共i个字符组成的子串编码个数。
		
		但是这里的‘0’是不编码的，所以说就有可能出现断层，导致编码数为0，例如： 
		当出现“01”时，由于第一个元素就是为‘0’所以就没办法往后继续计数了（二位组合的01不代表编码1，所以01也没有意义）。
		
		那么现在分析连续出现的两位数int tmp;(假设已经完成string to num的操作)，那么它存在以下几种情况： 
		情况一 
		10 <= tmp <= 26 这个时候一定满足一个条件，dp(i+1)至少包含了dp(i-1)的内容（即s[0]到s[i-2]的内容），
		因为s[i-1]s[i]组合的子串是一个可编码的二位数，例如当子串为xxxx26，则一定能完成编码xxxxZ，而xxxx编码的个数为dp(i-1)。
		
		情况二 
		然后在考虑‘0’的情况，当s[i]！=’0’时，这时候tmp不可能的值是00,10,20 … 90，那么对于任意一个两位数（这个两位数可能大于26）例如31，
		那么它至少可以完成一种编码，即CA，假设有一个串是xxxxx31，dp(i)表示xxxxx3的个数，那么此时dp(i+1)=dp(i+1)+dp(i)，
		当然如果是xxxxx30，最后一个0就没办法编码了。
		
		根据公式来看，全集是dp(i)+dp(i-1),以上两种情况，分别处理‘0’变量，分步骤求解。 
		这种分开求解，考虑了10，20这种情况。
	 * 
	 * 
	 * 
	 * 
	 * 
	 */
	 public int numDecodings(String s) {
		 	//判断是否为Null
		   if(s == null || s.length() == 0) return 0;
		   //获取s的长度 
		   int n = s.length();
		   //创建一个dp数组 
		   int[] dp = new int[n + 1];
		    dp[0] = 1;
		    //创建dp[1],存储可以解码的长度,判断s是否为0
		    dp[1] = s.charAt(0) == '0' ? 0 : 1;
		    for(int i = 2; i <= n; i++) {
		    	//获取s的第二个元素
				char one = s.charAt(i-1);
				if( one != '0' )  dp[i] += dp[i-1];
		        //判断前一个数是否有值
		        if(s.charAt(i - 2) == '0') continue;
		        //获取2个数字,
		        int two = Integer.valueOf(s.substring(i - 2, i));
		        if(two <= 26) dp[i] += dp[i - 2];
		    }
		    return dp[n];   
		    
	          
	 
	 }
}
